class TreeNote:
    def __init__(self, list_in, start, end):
        self.contain = [start, end]
        self.mid = (start + end) // 2
        self.left = TreeNote(list_in[:self.mid-start+1], start, self.mid) if start != end else None
        self.right = TreeNote(list_in[self.mid-start+1:], self.mid+1, end) if start != end else None
        self.val = self.left.val + self.right.val if start != end else list_in[0]

    def update(self, i, val, old_val):
        self.val += val - old_val
        if i <= self.mid and self.left:
            self.left.update(i, val, old_val)
        elif i > self.mid and self.right:
            self.right.update(i, val, old_val)

    def sumRange(self, i: int, j: int) -> int:
        if i == self.contain[0] and j == self.contain[1]:
            return self.val
        elif i > self.mid:
            return self.right.sumRange(i, j)
        elif j <= self.mid:
            return self.left.sumRange(i, j)
        else:
            return self.left.sumRange(i, self.mid) + self.right.sumRange(self.mid+1, j)


class NumArray:
    def __init__(self, nums: list):
        self.root = TreeNote(nums, 0, len(nums) - 1) if nums else None
        self.nums = nums

    def update(self, i: int, val: int) -> None:
        self.root.update(i, val, self.nums[i])
        self.nums[i] = val

    def sumRange(self, i: int, j: int) -> int:
        return self.root.sumRange(i, j)


class NumArray2:
    """会超时"""
    def __init__(self, nums: list):
        self.nums = nums

    def update(self, i: int, val: int) -> None:
        self.nums[i] = val

    def sumRange(self, i: int, j: int) -> int:
        res = 0
        for index in range(i, j+1):
            res += self.nums[index]
        return res


a = NumArray([1, 3, 5])
print(a.sumRange(0, 2))
print(a.update(1, 2))
print(a.sumRange(0, 2))
print(a.update(2, 7))
print(a.sumRange(0, 2))
# ["NumArray","sumRange","sumRange","sumRange","update","update","update","sumRange","update","sumRange","update"]
# [[[0,9,5,7,3]],[4,4],[2,4],[3,3],[4,5],[1,7],[0,8],[1,2],[1,9],[4,4],[3,4]]
a = NumArray([0, 9, 5, 7, 3])
print(a.sumRange(4, 4))
print(a.sumRange(2, 4))
print(a.sumRange(3, 3))
print(a.update(4, 5))
print(a.update(1, 7))
print(a.update(0, 8))
print(a.sumRange(1, 2))
print(a.update(1, 9))
print(a.sumRange(4, 4))
print(a.sumRange(3, 4))
